package day_2022_12_to_3.year2023;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author haomin
 * @date 2023/03/12 23:00
 **/
public class Day3_12_Num1617 {
    class Solution {
        final int N = 20,M = 2*N,INF = 0x3f3f3f3f;

        int[] h = new int[N];
        int[] e = new int[M];
        int[] ne = new int[M];
        int[] dist = new int[N];
        int[] res;
        int[] p = new int[N];
        int idx,target,n,max;

        public int find(int x){
            if(p[x] != x)p[x] = find(p[x]);
            return p[x];
        }

        public void add(int a,int b){
            e[idx] = b;ne[idx] = h[a];h[a] = idx++;
        }

        public int[] countSubgraphsForEachDiameter(int n, int[][] edges) {
            this.n = n;
            int m = edges.length;
            res = new int[n-1];
            for(int i = 0;i < (1 << m);i++){
                Arrays.fill(h,-1);
                idx = 0;
                for(int j = 0;j < N;j++)p[j] = j;

                int root = 1;
                Set<Integer> set = new HashSet<>();
                for(int j = 0;j < m;j++){
                    if((i >> j & 1) == 1){
                        int[] edge = edges[j];
                        int a = edge[0],b = edge[1];
                        root = a;
                        add(a,b);add(b,a);
                        set.add(a);
                        set.add(b);
                        p[find(a)] = find(b);
                    }
                }
                if(!check(set))continue;
                // System.out.println(i);
                Arrays.fill(dist,INF);
                dist[root] = 0;
                max = 0;
                dfs(root,i);
                // System.out.print(i+" t "+root+" "+target+" ");
                Arrays.fill(dist,INF);
                dist[target] = 0;
                max = 0;
                // if(target == 0)continue;
                dfs(target,i);
                // System.out.println(target+" p "+max);
                if(max != 0)res[max-1]++;
            }
            return res;
        }

        public boolean check(Set<Integer> set){
            int cnt = 0;
            for (Integer integer : set) {
                if(p[integer] == integer)cnt++;
            }
            return cnt == 1;
        }

        public void dfs(int u,int state){
            for(int i = h[u];i != -1;i = ne[i]){
                int j = e[i];
                // if(state == 3) System.out.println(u+" s "+j);
                if(dist[j] != INF)continue;
                dist[j] = dist[u]+1;
                if(dist[j] > max){
                    max = dist[j];
                    target = j;
                }
                dfs(j,state);
            }
        }
    }
}